package com.dhnsoft.数据结构与算法.链表;

import java.util.Stack;

/**
 * ClassName: SingleLinkedListDemo
 * Package: com.dhnsoft.数据结构与算法.链表
 * Description:
 *
 * @Author dhn
 * @Create 2024/3/4 10:35
 * @Version 1.0
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1,"宋江","及时雨");
        HeroNode h2 = new HeroNode(3,"卢俊义","玉麒麟");
        HeroNode h3 = new HeroNode(5,"吴用","智多星");
        HeroNode h4 = new HeroNode(7,"林冲","豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addByOrder(h2);
        singleLinkedList.addByOrder(h1);
        singleLinkedList.addByOrder(h4);
        singleLinkedList.addByOrder(h3);
        System.out.println("------第一个链表");
        singleLinkedList.list();


        HeroNode h5 = new HeroNode(2,"宋江","及时雨");
        HeroNode h6 = new HeroNode(4,"卢俊义","玉麒麟");
        HeroNode h7 = new HeroNode(6,"吴用","智多星");
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addByOrder(h5);
        singleLinkedList2.addByOrder(h6);
        singleLinkedList2.addByOrder(h7);
        System.out.println("------第二个链表");
        singleLinkedList2.list();
//        reverseList(singleLinkedList.getHead());
//        reversePrint(singleLinkedList.getHead());
        getMergeList(singleLinkedList.getHead(), singleLinkedList2.getHead());
        System.out.println("------合并后的链表");
        singleLinkedList.list();



        //测试修改节点的代码
//        HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟~~");
//        singleLinkedList.update(newHeroNode);
//        singleLinkedList.list();
//
//        //删除某一个节点
//        HeroNode delHeroNode = new HeroNode(2,"小卢","玉麒麟");
//        singleLinkedList.delete(delHeroNode);
//        singleLinkedList.list();
//
//        //求单链表有效节点的个数
//        System.out.println(getLength(singleLinkedList.getHead()));
//
//        //测试是否得到倒数第k个节点
//        HeroNode lastIndexNumNode = getLastIndexNumNode(singleLinkedList.getHead(), 1);
//        System.out.println(lastIndexNumNode);


    }
    //合并两个有序的单链表，合并之后的链表依然有序
    public static void getMergeList(HeroNode h1,HeroNode h2){
        if(h1==null){
            return;
        }
        if(h2==null){
            return;
        }
        HeroNode t1 = h1.next;
        HeroNode t2 = h2.next;
        HeroNode cur1 = null;
        HeroNode cur2 = null;
        HeroNode newList = new HeroNode(0,"","");
        while (t2!=null||t1!=null){
            if(t1.no<t2.no&&t1.next.no>t2.no){
                cur1 = t1.next;
                cur2 = t2.next;
                t2.next = t1.next;
                t1.next = t2;
                t2 = cur2;
                t1 = cur1;
            }

        }

    }


    //方法：获取到单链表的节点个数（如果是带头节点的链表，需求不统计头节点）
    public static int getLength(HeroNode head){
        if(head==null){
            return 0;
        }
        HeroNode cur = head.next;
        int lens = 0;
        while(cur!=null){
            lens++;
            cur = cur.next;
        }
        return lens;
    }

    //查找单链表中的倒数第k个节点
    public static HeroNode getLastIndexNumNode(HeroNode head,int index){
        if(head==null){
            return null;
        }
        int len = getLength(head);
        if(len<=0||index>len){
            return null;
        }
        int num = len-index;
        HeroNode temp = head.next;
        for (int i = 0 ; i<num;i++){
            temp = temp.next;
        }
        return temp;
    }

    //将单链表进行反转
    public static void reverseList(HeroNode head){
        if(head.next==null||head.next.next==null){
            return;
        }
        //定义一个辅助指针变量，帮助我们遍历原来的链表
        HeroNode cur = head.next;
        HeroNode next = null;//指向当前节点[cur]的下一个节点
        HeroNode reverseHead = new HeroNode(0,"","");
        //遍历原来的链表，每遍历一个节点，就将其取出，并放在新的链表reverseHead的最前端
        while (cur!=null){
            next = cur.next; //先暂时保存当前节点的下一个节点，因为后面需要使用
            cur.next = reverseHead.next;//将当前节点链接上新链表的下一个节点
            reverseHead.next = cur;//将新链表的下一个节点指向刚刚链接上的节点
            cur = next;//再当前节点往后移动
        }
        head.next = reverseHead.next;

    }
    //可以利用栈这个数据结构，将各个节点压入到栈中，然后利用栈的先进后出的特点，实现逆序打印链表的效果
    public static void reversePrint(HeroNode head){
        if(head==null){
            return;
        }
        HeroNode temp = head.next;
        Stack<HeroNode> stack = new Stack<>();
        while(temp!=null){
            stack.push(temp);
            temp = temp.next;
        }
        //逆序打印
        while (stack.size()!=0){
            System.out.println(stack.pop());
        }
    }

}

//定义SingleLinkedList管理我们的英雄
class SingleLinkedList{
    //初始化一个头节点
    private HeroNode head = new HeroNode(0,"","");

    public HeroNode getHead() {
        return head;
    }

    public void setHead(HeroNode head) {
        this.head = head;
    }

    //添加节点到单向链表
    public void add(HeroNode node){
        //因为头节点是不能动的，所以我们需要一个辅助节点来移动
        HeroNode temp = head;
        while (true){
            //遇到最后一个节点跳出循环
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next = node;

    }
    //显示链表（遍历）
    public void list(){
        //判断链表是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            //链表一定得后移
            temp = temp.next;
        }
    }
    //按顺序添加节点，重复得不添加
    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;//声明一个flag来判断是否重复
        while (true){
            //判断是否到达最后一个节点，是的话跳出循环
            if(temp.next==null){
                break;
            }
            //判断当前节点的下一个节点是否大于要插入的目标节点
            if(temp.next.no>heroNode.no){
                break;
            }
            else if(temp.no==heroNode.no){//检查是否重复，若重复则跳出，并标记
                flag=true;
                break;
            }
            temp = temp.next;
        }
        //判断如果重复则不能添加
        if(flag){
            System.out.printf("准备插入的英雄的编号%d已经存在\n",heroNode.no);
        }
        else{
            //将要插入节点的next指向temp的下一个节点
            heroNode.next = temp.next;
            //将temp的next指向要插入的节点
            temp.next = heroNode;
        }

    }
    //修改节点代码
    public void update(HeroNode heroNode){
        //判断是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;
        while(true){
            if(temp==null){
                break;
            }
            if(heroNode.no==temp.no){
                flag = true;
                break;
            }
            temp = temp.next;

        }
        if(flag){
            temp.nickName=heroNode.nickName;
            temp.name=heroNode.name;
        }
        else{
            System.out.printf("没有找到编号%d的节点，不能修改\n",heroNode.no);
        }
    }

    //删除某一个节点
    public void delete(HeroNode heroNode){
        //判断是否为空
        if(head.next==null){
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head;
        boolean flag = false;
        while (true){
            if(temp.next==null){
                break;
            }
            if(temp.next.no==heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if(flag){
            temp.next = temp.next.next;
        }
        else{
            System.out.printf("没有找到编号%d的节点，不能修改\n",heroNode.no);
        }
    }



}




//定义一个HeroNode
class HeroNode{
    int no;
    String name;
    String nickName;
    HeroNode next; //指向下一个节点

    public HeroNode(int no,String name,String nickName){
        this.name = name;
        this.no = no;
        this.nickName = nickName;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getNickName() {
        return nickName;
    }

    public void setNickName(String nickName) {
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '\'' +
                "" +
                '}';
    }
}
